/*
 * @Author: your name
 * @Date: 2024-06-19 14:01:20
 * @LastEditTime: 2024-06-19 14:11:25
 * @LastEditors: your name
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\63.不同路径-ii.cpp
 */
/*
 * @lc app=leetcode.cn id=63 lang=cpp
 *
 * [63] 不同路径 II
 */

// @lc code=start
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        // 定义dp表
        vector<vector<int>>dp(obstacleGrid.size(), vector(obstacleGrid[0].size(), 0));
        // 处理边界，并且边界可能存在障碍
        int flag = 0;
        for (int  i = 0; i < dp.size(); i++){
            if(obstacleGrid[i][0] == 0 && flag == 0){
                dp[i][0] = 1;
            }else{
                flag = 1;
            }
        }
        flag = 0;
        for(int i = 0; i < dp[0].size(); i++){
            if(obstacleGrid[0][i] == 0 && flag == 0){
                dp[0][i] = 1;
            }else{
                flag = 1;
            }
        }
        for(int i = 1; i < dp.size(); i++){
            for(int j = 1; j < dp[0].size(); j++){
                if(obstacleGrid[i][j] == 1){
                    // 有障碍物
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[dp.size()-1][dp[0].size()-1];
        
    }
};
// @lc code=end

